
def dijkstra_find(graph, costs, parents, processed):
    node = find_lowest_cost_node(costs)
    while node is not None:
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = find_lowest_cost_node(costs)

def find_lowest_cost_node(costs):
    lowest_cost = float('inf')
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

def make_graph_info():
    graph = {}
    graph['A'] = {'B':6, 'C':2}
    graph['B'] = {'D':1}
    graph['C'] = {'B':3, 'D':5}
    graph['D'] = {}
    costs = {}
    costs['B'] = 6
    costs['C'] = 2
    costs['D'] = float('inf')
    parents = {}
    parents['A'] = None
    parents['B'] = 'A'
    parents['C'] = 'A'
    parents['D'] = None
    return graph, costs, parents



if __name__ == '__main__':
    graph, costs, parents = make_graph_info()
    processed = []
    dijkstra_find(graph, costs, parents, processed)